/*
https://leetcode-cn.com/problems/create-maximum-number/solution/pin-jie-zui-da-shu-by-leetcode-solution/
 */
import java.util.Arrays;

public class Solution321 {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int[] ans=new int[k];
        for (int i=0;i<=k;i++){
            int j=k-i;
            if (i>nums1.length || j>nums2.length){
                continue;
            }
            int[] a1=work(nums1,i);
            int[] a2=work(nums2,j);
            int m=0,n=0,cur=0;
            int[] t=new int[k];
            while (cur<k){
                if (compare(a1,m,a2,n)==1){
                    t[cur]=a1[m];
                    m++;
                }else{
                    t[cur]=a2[n];
                    n++;
                }
                cur++;
            }
            if (compare(ans,0,t,0)==-1){
                ans=t;
            }
        }
        return ans;
    }

    private int compare(int[] a1, int m, int[] a2, int n) {
        if (m==a1.length){
            return -1;
        }else if (n==a2.length){
            return 1;
        }else{
            while (m<a1.length && n<a2.length){
                if (a1[m]!=a2[n]){
                    return a1[m]<a2[n]?-1:1;
                }
                m++;
                n++;
            }
            return (a1.length-m)>(a2.length-n)?1:-1;
        }
    }

    private int[] work(int[] nums, int t) {
        int[] stack=new int[t];
        int top=-1;
        int remain=nums.length-t;
        for (int i=0;i<nums.length;i++){
            while (top!=-1 && nums[i]>stack[top] && remain>0){
                top--;
                remain--;
            }
            if (top==t-1){
                remain--;
            }else{
                top++;
                stack[top]=nums[i];
            }
        }
        return stack;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new Solution321().maxNumber(new int[]{3,4,6,5},new int[]{9,1,2,5,8,3},5)));
    }
}
